package algorithm.interview;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// java分解因数 因数分解
public class FactoringJava {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str  = n + " = " + factoring(n);
        System.out.println(str);

    }

    private static String factoring(int a) {
//i先是质数2。
//往后的如果是合数，合数是它前面的质因子的乘积，目标不可能再被这个合数整除了
// （如果可以被合数整除，代表着可以被合数的质因子所整除。
// 但是遍历到合数这里时，已经while循环处理过、被整除过了，不可能再被整除。） 所以往后只能是质因子有机会。

        List<Integer> list = new ArrayList<Integer>();
        for (int i = 2; i <= Math.sqrt(a); i++) {
            //i是质因子从2开始。
            while (a % i == 0) {
                list.add(i);
                a = a / i;
            }
        }

        //如果最后a是质数
        if (a > 1) {
            list.add(a);
        }

        //结束。
        StringBuilder res = new StringBuilder(list.get(0).toString()); // 第一个质因子
        for (int i = 1; i < list.size(); i++) {
            res.append(" * " + list.get(i));
        }
        return res.toString();
    }

}
